package com.eric.demo.alitest;


/**
 * @author guangyin.zhang
 * @since 2019/7/17
 * 解题思路
 * 1. 定义一个内部结点类，存放当前数据data和下一个指针next
 * 2. MyLinkList类型定义属性:第一个节点数据first，最后一个节点数据current，链表长度size
 * 3. add逻辑:
 *      3.1 first为空，第一次添加，first和current同时指向新节点，size加1
 *      3.2 first不为空，先把current.next指向新节点，再把current指向新节点，size加1
 * 4. remove逻辑:
 *      4.1 寻找待删除的数据前一个节点prex
 *      4.2 prex.next = prex.next.next, size-1
 *
 * 备注：线程不安全
 */
public class MyLinkList<T>{

    /**
     * 指向第一个节点的工作指针
     */
    private MyNode<T> first;

    /**
     * 指向最后一个节点的工作指针
     */
    private MyNode<T> current;

    /**
     * 统计链表长度
     */
    private int size=0;

    /**
     * 添加节点
     */
    public void add(T data){
        MyNode<T> newNode=new MyNode<T>();
        newNode.data=data;

        if(first==null){
            first=newNode;
            current=newNode;
            size++;
            return;
        }
        current.next=newNode;
        current=newNode;
        size++;
    }

    /**
     * 移除数据
     * @param data
     */
    public void remove(T data){
        int index = -1;
        do{
            index = getIndex(data);
            remove(index);
        }while (index > -1);

    }


    /**
     * 得到指定索引的数据
     * @param index
     * @return 数据
     */
    public T get(int index){
        return getNode(index).next.data;
    }
    /**
     * 得到指定索引的前一个节点
     * @param index
     * @return
     */
    private MyNode<T> getNode(int index) {
        MyNode<T> node=null;
        if(index == 0){
            //插入到第一个
            return null;
        }
        if(index < size){
            //插入中间
            node = first;
            for(int i=1; i<index; i++){
                node=node.next;
            }
            return node;
        }
        return current;
    }


    /**
     * 通过数据查找第一次出现的索引
     * @param data
     * @return
     */
    private int getIndex(T data) {
        MyNode node=first;
        for(int i=0;i<size;i++){
            if(node.data.equals(data)){
                return i;
            }
            node=node.next;
        }
        return -1;
    }

    /**
     * 移除指定索引的数据
     * @param index
     */
    private void remove(int index){
        MyNode prev = getNode(index);
        MyNode node = getNode(index+1);
        prev.next = node.next;
        size--;
    }

    private static class MyNode<T>{
        T data;
        MyNode<T> next;
    }

}
